package com.lun.swordtowardoffer2.c01;

public class MaxProduct {
	
	//1. 用哈希表记录字符串中出现的字符
	public int maxProduct(String[] words) {
		boolean[][] flags = new boolean[words.length][26];
		
		for(int i = 0; i < words.length; i++) {
			for(int j = 0; j < words[i].length(); j++) {
				flags[i][words[i].charAt(j) - 'a'] = true;
			}
		}
		
		int result = 0;
		for(int i = 0; i < words.length; i++) {
			for(int j = i + 1; j < words.length; j++) {
				int k = 0;
				
				while(k < 26) {
					if(flags[i][k] && flags[j][k])
						break;
					k++;
				}
				
				if(k == 26)
					result = Math.max(result, words[i].length() * words[j].length());
			}
		}
		
		return result;
	}
	
	//2. 用整数的二进制数位记录字符串中出现的字符
	public int maxProduct2(String[] words) {
		int[] flags = new int[words.length];
		
		for(int i = 0; i < words.length; i++) {
			for(int j = 0; j < words[i].length(); j++) {
				flags[i] |= (1 << (words[i].charAt(j) - 'a'));
			}
		}
		
		int result = 0;
		for(int i = 0; i < words.length; i++) {
			for(int j = i + 1; j < words.length; j++) {
				if((flags[i] & flags[j]) == 0) {
					int prod = words[i].length() * words[j].length();
					result = Math.max(result, prod);
				}
			}
		}
		
		return result;
	}
	
}
